package dp01;

/**
 * 动态规划
 * 题目：解码方法
 * https://leetcode.cn/problems/decode-ways/solutions/2252354/91-jie-ma-fang-fa-by-stormsunshine-62t0/
 */
public class Solution {
    //方法1
    public int numDecodings(String s) {
        char[] chars = s.toCharArray();
        int n = chars.length;
        int[] dp = new int[n];
        if(chars[0] != '0') dp[0] = 1 ;
        if (n == 1) return dp[0];
        if(chars[1] != '0' && chars[0] != '0') dp[1] += 1;
        int t = (chars[0] - '0') * 10 +( chars[1] - '0');
        if(t >= 10 && t <= 26) dp[1] += 1;
        for (int i = 2; i < n; i++) {
            if(chars[i] != '0') {          //单解码成功
                dp[i] += dp[i-1];
            }
            int tt = (chars[i-1] - '0') * 10 + (chars[i] - '0');   //两解码成功
            if(tt >= 10 && tt <= 26) dp[i] += dp[i-2];
        }
        return dp[n-1];
    }

    /**
     * 结点优化
     */
    public int numDecodings1(String s) {
        int n = s.length();
        char[] chars = s.toCharArray();
        int[] dp = new int[n+1];
        dp[0] = 1;
        if(chars[1-1] != '0') dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            if(chars[i-1] != '0') dp[i] += dp[i-1];
            int t = (chars[i-1] - '0') * 10 + (chars[i] - '0');
            if(t >= 10 && t <= 26) dp[i] += dp[i-2];
        }
        return dp[n];
    }

}
